package BFS解决FloodFill算法;

import java.util.*;

public class 高尔夫砍树 {
    int [] dx = {1,-1,0,0};
    int [] dy = {0,0,1,-1};
    int m,n;
    public int cutOffTree(List<List<Integer>> f)
    {
      m = f.size();n = f.get(0).size();
      //1.准备工作，确定砍树顺序
        List<int []> trees = new ArrayList<>();
        for(int i = 0 ; i<m;i++)
            for(int j = 0;j<n;j++)
                if(f.get(i).get(j) >1)
                    trees.add(new int[]{i,j});
        Collections.sort(trees,(a,b)->
        {
           return  f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
        });

        //2.按照顺序排序
        int ret = 0;
        int bx = 0 ,by = 0;
        for(int [] tree:trees)
        {
            int x = tree[0],y = tree[1];
            int step = bfs(f,bx,by,x,y);
            if(step == -1 ) return -1;
            ret += step;
            bx = x;by = y;

        }
        return ret;

    }

    public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey)

    {
        if(bx ==ex &&  by == ey) return 0;
        Queue<int [] > q =new LinkedList<>();
        boolean [][] vis = new boolean[m][n];
        q.add(new int []{bx,by});
        vis[bx][by] = true;

        int step = 0;
        while(!q.isEmpty())
        {
            int sz = q.size();
            while(sz-- != 0)
            {
                int [] cur =q.poll();
                int x = cur[0],y = cur[1];
                for(int i = 0 ; i <4;i++)
                {
                    int x1 = x+dx[i];
                    int y1 = y+dy[i];
                    if(x1>=0 && x1<m && y1>=0 && y1<n && !vis[x1][y1] && f.get(x1).get(y1) != 0)
                    {
                            if(x1 == ex && y1 == ey) return step+1;

                            q.add(new int[]{x1,y1});
                            vis[x1][y1] = true;
                    }

                }
            }
        }
        return -1;
    }
}
